package com.mlh.Slidingwindow;

import java.util.*;

/**
 * @author 缪林辉
 * @date 2024/8/14 23:59
 * @DESCRIPTION
 */
// 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
// 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
// 输入: s = "cbaebabacd", p = "abc"
// 输出: [0,6]
// 解释:
// 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
// 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
public class 找到字符串中所有字母异位词 {
    // 根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。
    // 因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，
    // 所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，
    // 并在滑动中维护窗口中每种字母的数量；
    // 当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。
    public List<Integer> method1(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

    public List<Integer> practice(String s, String p) {
        if(s.length()<p.length()){
            return new ArrayList<>();
        }
        int pLen=p.length();
        int[]sliding=new int[26];
        int[]pCount=new int[26];//用于记录p字符串中有哪些字符及数量
        List<Integer>res=new ArrayList<>();
        //第一次开始滑动窗口  将滑动窗口填满
        // 这里的滑动窗口大小是固定的
        for (int i = 0; i < pLen; i++) {
            ++sliding[s.charAt(i)-'a'];
            ++pCount[p.charAt(i)-'a'];
        }
        if(Arrays.equals(sliding,pCount)){
            res.add(0);
        }
        //开始滑动窗口
        for (int i = 0; i < s.length()-pLen; i++) {
            --sliding[s.charAt(i)-'a'];
            ++sliding[s.charAt(pLen+i)-'a'];
            if(Arrays.equals(sliding,pCount)){
                res.add(i+1);
            }
        }
        return res;
    }

    public List<Integer> practice2(String s, String p) {
        int sLen=s.length(),pLen=p.length();
        List<Integer>res=new ArrayList<>();
        if(sLen<pLen) {
            return res;
        }
        int[]sNum=new int[26],pNum=new int[26];
        for (int i = 0; i < pLen; i++) {
            ++pNum[p.charAt(i)-'a'];
            ++sNum[s.charAt(i)-'a'];
        }
        if(Arrays.equals(sNum,pNum)){
            res.add(0);
        }
        for (int i = 1; i <sLen-pLen+1; i++) {
            --sNum[s.charAt(i-1)-'a'];
            ++sNum[s.charAt(i+pLen-1)-'a'];
            if(Arrays.equals(sNum,pNum)){
                res.add(i);
            }
        }
        return res;
    }
}
